//
//  ArraySort.swift
//  Swift刷算法
//
//  Created by 卢悦明 on 2020/12/25.
//

import Foundation

class ArraySort: NSObject {

    /// 88. 合并两个有序数组
    static func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var index1 = m - 1
        var index2 = n - 1
        var countIndex = m + n - 1
        while index2 >= 0 {
            if index1 >= 0 && nums1[index1] > nums2[index2] {
                nums1[countIndex] = nums1[index1]
                countIndex -= 1
                index1 -= 1
            } else {
                nums1[countIndex] = nums2[index2]
                countIndex -= 1
                index2 -= 1
            }
        }
    }
    
    /// 荷兰国旗问题
    static func sortColors(_ nums: inout [Int]) {
        var i = 0, l = 0, r = nums.count - 1
        while i <= r {
            let num = nums[i]
            if num == 0 {
                (nums[i], nums[l]) = (nums[l], nums[i])
                i += 1
                l += 1
            } else if num == 2 {
                (nums[i], nums[r]) = (nums[r], nums[i])
                r -= 1
            } else {
                i += 1
            }
        }
    }
    
    /// 部分排序
    static func subSort(_ array: [Int]) -> [Int] {
        var right = -1
        var left = -1
        guard array.count > 0 else {
            return [left, right]
        }
        var maxNum = array[0]
        var minNum = array[array.count - 1]
        
        for index in 1..<array.count {
            let num = array[index]
            if num >= maxNum {
                maxNum = num
            } else {
                right = index
            }
        }
        
        if right == -1 {
            return [left, right]
        }
        
        for index in (0..<array.count - 1).reversed(){
            let num = array[index]
            if num <= minNum {
                minNum = num
            } else {
                left = index
            }
        }
        
        return [left, right]
    }
    
}


fileprivate extension ArraySort {
    /// 交换
    static func swip(i: Int, j: Int, nums: inout [Int]) {
        (nums[i], nums[j]) = (nums[j], nums[i])
    }
}
